/*
 * Color Thief v2.0
 * by Lokesh Dhakar - http://www.lokeshdhakar.com
 *
 * Thanks
 * ------
 * Nick Rabinowitz - For creating quantize.js.
 * John Schulz - For clean up and optimization. @JFSIII
 * Nathan Spady - For adding drag and drop support to the demo page.
 *
 * License
 * -------
 * Copyright 2011, 2015 Lokesh Dhakar
 * Released under the MIT license
 * https://raw.githubusercontent.com/lokesh/color-thief/master/LICENSE
 *
 * @license
 */

/*
  CanvasImage Class
  Class that wraps the html image element and canvas.
  It also simplifies some of the canvas context manipulation
  with a set of helper functions.
*/
class CanvasImage {
  // 构造函数，接收一个image对象和一个bounding对象
  constructor(image, bounding) {
    // 创建一个canvas元素
    this.canvas = document.createElement("canvas");
    // 获取canvas的上下文
    this.context = this.canvas.getContext("2d");

    // 将canvas添加到body中
    document.body.appendChild(this.canvas);

    // 设置canvas的宽度和高度为image的宽度和高度
    this.width = this.canvas.width = image.width;
    this.height = this.canvas.height = image.height;

    // 如果bounding是一个数组，则绘制image的指定区域到canvas中
    if (bounding instanceof Array) {
      this.context.drawImage(
        image,
        bounding[0],
        bounding[1],
        bounding[2],
        bounding[3],
        bounding[0],
        bounding[1],
        bounding[2],
        bounding[3]
      );
      this.bounding = bounding;
    } else {
      // 否则绘制整个image到canvas中
      this.context.drawImage(image, 0, 0, this.width, this.height);
    }
  }
  // 清空canvas
  clear() {
    this.context.clearRect(0, 0, this.width, this.height);
  }
  // 更新canvas中的图像数据
  update(imageData) {
    this.context.putImageData(imageData, 0, 0);
  }
  // 获取canvas中的像素数量
  getPixelCount() {
    var bounding = this.bounding;
    // 如果bounding是一个数组，则返回指定区域的像素数量
    if (bounding && bounding.length == 4) {
      return bounding[2] * bounding[3];
    }
    // 否则返回整个canvas的像素数量
    return this.width * this.height;
  }
  // 获取canvas中的图像数据
  getImageData() {
    var bounding = this.bounding;
    // 如果bounding是一个数组，则返回指定区域的图像数据
    if (bounding instanceof Array) {
      return this.context.getImageData(
        bounding[0],
        bounding[1],
        bounding[2],
        bounding[3]
      );
    }
    // 否则返回整个canvas的图像数据
    return this.context.getImageData(0, 0, this.width, this.height);
  }
  // 移除canvas
  removeCanvas() {
    this.canvas.parentNode.removeChild(this.canvas);
  }
}

class ColorThief {
  constructor() {}
  /*
   * getColor(sourceImage[, quality])
   * returns {r: num, g: num, b: num}
   *
   * Use the median cut algorithm provided by quantize.js to cluster similar
   * colors and return the base color from the largest cluster.
   *
   * Quality is an optional argument. It needs to be an integer. 1 is the highest quality settings.
   * 10 is the default. There is a trade-off between quality and speed. The bigger the number, the
   * faster a color will be returned but the greater the likelihood that it will not be the visually
   * most dominant color.
   *
   * */
  getColor(sourceImage, quality, bounding) {
    var palette = this.getPalette(sourceImage, 5, quality, bounding);
    var dominantColor = palette[0];
    return dominantColor;
  }
  /*
   * getPalette(sourceImage[, colorCount, quality])
   * returns array[ {r: num, g: num, b: num}, {r: num, g: num, b: num}, ...]
   *
   * Use the median cut algorithm provided by quantize.js to cluster similar colors.
   *
   * colorCount determines the size of the palette; the number of colors returned. If not set, it
   * defaults to 10.
   *
   * BUGGY: Function does not always return the requested amount of colors. It can be +/- 2.
   *
   * quality is an optional argument. It needs to be an integer. 1 is the highest quality settings.
   * 10 is the default. There is a trade-off between quality and speed. The bigger the number, the
   * faster the palette generation but the greater the likelihood that colors will be missed.
   *
   *
   */
  getPalette(sourceImage, colorCount, quality, bounding) {
    if (
      typeof colorCount === "undefined" ||
      colorCount < 2 ||
      colorCount > 256
    ) {
      colorCount = 10;
    }

    if (quality instanceof Array) {
      bounding = quality;
      quality = 10;
    } else if (typeof quality === "undefined" || quality < 1) {
      quality = 10;
    }

    // Create custom CanvasImage object
    var image = new CanvasImage(sourceImage, bounding);
    var imageData = image.getImageData();

    var pixels = imageData.data;
    var pixelCount = image.getPixelCount();

    // Store the RGB values in an array format suitable for quantize function
    var pixelArray = [];
    for (var i = 0, offset, r, g, b, a; i < pixelCount; i = i + quality) {
      offset = i * 4;
      r = pixels[offset + 0];
      g = pixels[offset + 1];
      b = pixels[offset + 2];
      a = pixels[offset + 3];
      // If pixel is mostly opaque and not white
      if (a >= 125) {
        //if (!(r > 250 && g > 250 && b > 250)) {
        pixelArray.push([r, g, b]);
        //}
      }
    }

    // Send array to quantize function which clusters values
    // using median cut algorithm
    var cmap = MMCQ.quantize(pixelArray, colorCount);
    var palette = cmap ? cmap.palette() : null;

    // Clean up
    image.removeCanvas();

    return palette;
  }
  getColorFromUrl(imageUrl, callback, quality) {
    sourceImage = document.createElement("img");
    var thief = this;
    sourceImage.addEventListener("load", function () {
      var palette = thief.getPalette(sourceImage, 5, quality);
      var dominantColor = palette[0];
      callback(dominantColor, imageUrl);
    });
    sourceImage.src = imageUrl;
  }
  getImageData(imageUrl, callback) {
    xhr = new XMLHttpRequest();
    xhr.open("GET", imageUrl, true);
    xhr.responseType = "arraybuffer";
    xhr.onload = function (e) {
      if (this.status == 200) {
        uInt8Array = new Uint8Array(this.response);
        i = uInt8Array.length;
        binaryString = new Array(i);
        for (var i = 0; i < uInt8Array.length; i++) {
          binaryString[i] = String.fromCharCode(uInt8Array[i]);
        }
        data = binaryString.join("");
        base64 = window.btoa(data);
        callback("data:image/png;base64," + base64);
      }
    };
    xhr.send();
  }
  getColorAsync(imageUrl, callback, quality) {
    var thief = this;
    this.getImageData(imageUrl, function (imageData) {
      sourceImage = document.createElement("img");
      sourceImage.addEventListener("load", function () {
        var palette = thief.getPalette(sourceImage, 5, quality);
        var dominantColor = palette[0];
        callback(dominantColor, this);
      });
      sourceImage.src = imageData;
    });
  }
}

/*!
 * quantize.js Copyright 2008 Nick Rabinowitz.
 * Licensed under the MIT license: http://www.opensource.org/licenses/mit-license.php
 * @license
 */

// fill out a couple protovis dependencies
/*!
 * Block below copied from Protovis: http://mbostock.github.com/protovis/
 * Copyright 2010 Stanford Visualization Group
 * Licensed under the BSD License: http://www.opensource.org/licenses/bsd-license.php
 * @license
 */
if (!pv) {
  var pv = {
    map: function (array, f) {
      var o = {};
      return f
        ? array.map(function (d, i) {
            o.index = i;
            return f.call(o, d);
          })
        : array.slice();
    },
    naturalOrder: function (a, b) {
      return a < b ? -1 : a > b ? 1 : 0;
    },
    sum: function (array, f) {
      var o = {};
      return array.reduce(
        f
          ? function (p, d, i) {
              o.index = i;
              return p + f.call(o, d);
            }
          : function (p, d) {
              return p + d;
            },
        0
      );
    },
    max: function (array, f) {
      return Math.max.apply(null, f ? pv.map(array, f) : array);
    },
  };
}

/**
 * Basic Javascript port of the MMCQ (modified median cut quantization)
 * algorithm from the Leptonica library (http://www.leptonica.com/).
 * Returns a color map you can use to map original pixels to the reduced
 * palette. Still a work in progress.
 *
 * @author Nick Rabinowitz
 * @example

// array of pixels as [R,G,B] arrays
var myPixels = [[190,197,190], [202,204,200], [207,214,210], [211,214,211], [205,207,207]
                // etc
                ];
var maxColors = 4;

var cmap = MMCQ.quantize(myPixels, maxColors);
var newPalette = cmap.palette();
var newPixels = myPixels.map(function(p) {
    return cmap.map(p);
});

 */
var MMCQ = (function () {
  // private constants
  var sigbits = 5,
    rshift = 8 - sigbits,
    maxIterations = 1000,
    fractByPopulations = 0.75;

  // get reduced-space color index for a pixel
  function getColorIndex(r, g, b) {
    return (r << (2 * sigbits)) + (g << sigbits) + b;
  }

  // Simple priority queue
  function PQueue(comparator) {
    var contents = [],
      sorted = false;

    function sort() {
      contents.sort(comparator);
      sorted = true;
    }

    return {
      push: function (o) {
        contents.push(o);
        sorted = false;
      },
      peek: function (index) {
        if (!sorted) sort();
        if (index === undefined) index = contents.length - 1;
        return contents[index];
      },
      pop: function () {
        if (!sorted) sort();
        return contents.pop();
      },
      size: function () {
        return contents.length;
      },
      map: function (f) {
        return contents.map(f);
      },
      debug: function () {
        if (!sorted) sort();
        return contents;
      },
    };
  }

  // 3d color space box
  class VBox {
    constructor(r1, r2, g1, g2, b1, b2, histo) {
      var vbox = this;
      vbox.r1 = r1;
      vbox.r2 = r2;
      vbox.g1 = g1;
      vbox.g2 = g2;
      vbox.b1 = b1;
      vbox.b2 = b2;
      vbox.histo = histo;
    }
    volume(force) {
      var vbox = this;
      if (!vbox._volume || force) {
        vbox._volume =
          (vbox.r2 - vbox.r1 + 1) *
          (vbox.g2 - vbox.g1 + 1) *
          (vbox.b2 - vbox.b1 + 1);
      }
      return vbox._volume;
    }
    count(force) {
      var vbox = this,
        histo = vbox.histo;
      if (!vbox._count_set || force) {
        var npix = 0,
          index,
          i,
          j,
          k;
        for (i = vbox.r1; i <= vbox.r2; i++) {
          for (j = vbox.g1; j <= vbox.g2; j++) {
            for (k = vbox.b1; k <= vbox.b2; k++) {
              index = getColorIndex(i, j, k);
              npix += histo[index] || 0;
            }
          }
        }
        vbox._count = npix;
        vbox._count_set = true;
      }
      return vbox._count;
    }
    copy() {
      var vbox = this;
      return new VBox(
        vbox.r1,
        vbox.r2,
        vbox.g1,
        vbox.g2,
        vbox.b1,
        vbox.b2,
        vbox.histo
      );
    }
    avg(force) {
      var vbox = this,
        histo = vbox.histo;
      if (!vbox._avg || force) {
        var ntot = 0,
          mult = 1 << (8 - sigbits),
          rsum = 0,
          gsum = 0,
          bsum = 0,
          hval,
          i,
          j,
          k,
          histoindex;
        for (i = vbox.r1; i <= vbox.r2; i++) {
          for (j = vbox.g1; j <= vbox.g2; j++) {
            for (k = vbox.b1; k <= vbox.b2; k++) {
              histoindex = getColorIndex(i, j, k);
              hval = histo[histoindex] || 0;
              ntot += hval;
              rsum += hval * (i + 0.5) * mult;
              gsum += hval * (j + 0.5) * mult;
              bsum += hval * (k + 0.5) * mult;
            }
          }
        }
        if (ntot) {
          vbox._avg = [~~(rsum / ntot), ~~(gsum / ntot), ~~(bsum / ntot)];
        } else {
          //                    console.log('empty box');
          vbox._avg = [
            ~~((mult * (vbox.r1 + vbox.r2 + 1)) / 2),
            ~~((mult * (vbox.g1 + vbox.g2 + 1)) / 2),
            ~~((mult * (vbox.b1 + vbox.b2 + 1)) / 2),
          ];
        }
      }
      return vbox._avg;
    }
    contains(pixel) {
      var vbox = this,
        rval = pixel[0] >> rshift;
      gval = pixel[1] >> rshift;
      bval = pixel[2] >> rshift;
      return (
        rval >= vbox.r1 &&
        rval <= vbox.r2 &&
        gval >= vbox.g1 &&
        gval <= vbox.g2 &&
        bval >= vbox.b1 &&
        bval <= vbox.b2
      );
    }
  }

  // Color map
  class CMap {
    constructor() {
      this.vboxes = new PQueue(function (a, b) {
        return pv.naturalOrder(
          a.vbox.count() * a.vbox.volume(),
          b.vbox.count() * b.vbox.volume()
        );
      });
    }
    push(vbox) {
      this.vboxes.push({
        vbox: vbox,
        color: vbox.avg(),
      });
    }
    palette() {
      return this.vboxes.map(function (vb) {
        return vb.color;
      });
    }
    size() {
      return this.vboxes.size();
    }
    map(color) {
      var vboxes = this.vboxes;
      for (var i = 0; i < vboxes.size(); i++) {
        if (vboxes.peek(i).vbox.contains(color)) {
          return vboxes.peek(i).color;
        }
      }
      return this.nearest(color);
    }
    nearest(color) {
      var vboxes = this.vboxes,
        d1,
        d2,
        pColor;
      for (var i = 0; i < vboxes.size(); i++) {
        d2 = Math.sqrt(
          Math.pow(color[0] - vboxes.peek(i).color[0], 2) +
            Math.pow(color[1] - vboxes.peek(i).color[1], 2) +
            Math.pow(color[2] - vboxes.peek(i).color[2], 2)
        );
        if (d2 < d1 || d1 === undefined) {
          d1 = d2;
          pColor = vboxes.peek(i).color;
        }
      }
      return pColor;
    }
    forcebw() {
      // XXX: won't  work yet
      var vboxes = this.vboxes;
      vboxes.sort(function (a, b) {
        return pv.naturalOrder(pv.sum(a.color), pv.sum(b.color));
      });

      // force darkest color to black if everything < 5
      var lowest = vboxes[0].color;
      if (lowest[0] < 5 && lowest[1] < 5 && lowest[2] < 5)
        vboxes[0].color = [0, 0, 0];

      // force lightest color to white if everything > 251
      var idx = vboxes.length - 1,
        highest = vboxes[idx].color;
      if (highest[0] > 251 && highest[1] > 251 && highest[2] > 251)
        vboxes[idx].color = [255, 255, 255];
    }
  }

  // histo (1-d array, giving the number of pixels in
  // each quantized region of color space), or null on error
  function getHisto(pixels) {
    var histosize = 1 << (3 * sigbits),
      histo = new Array(histosize),
      index,
      rval,
      gval,
      bval;
    pixels.forEach(function (pixel) {
      rval = pixel[0] >> rshift;
      gval = pixel[1] >> rshift;
      bval = pixel[2] >> rshift;
      index = getColorIndex(rval, gval, bval);
      histo[index] = (histo[index] || 0) + 1;
    });
    return histo;
  }

  function vboxFromPixels(pixels, histo) {
    var rmin = 1000000,
      rmax = 0,
      gmin = 1000000,
      gmax = 0,
      bmin = 1000000,
      bmax = 0,
      rval,
      gval,
      bval;
    // find min/max
    pixels.forEach(function (pixel) {
      rval = pixel[0] >> rshift;
      gval = pixel[1] >> rshift;
      bval = pixel[2] >> rshift;
      if (rval < rmin) rmin = rval;
      else if (rval > rmax) rmax = rval;
      if (gval < gmin) gmin = gval;
      else if (gval > gmax) gmax = gval;
      if (bval < bmin) bmin = bval;
      else if (bval > bmax) bmax = bval;
    });
    return new VBox(rmin, rmax, gmin, gmax, bmin, bmax, histo);
  }

  function medianCutApply(histo, vbox) {
    if (!vbox.count()) return;

    var rw = vbox.r2 - vbox.r1 + 1,
      gw = vbox.g2 - vbox.g1 + 1,
      bw = vbox.b2 - vbox.b1 + 1,
      maxw = pv.max([rw, gw, bw]);
    // only one pixel, no split
    if (vbox.count() == 1) {
      return [vbox.copy()];
    }
    /* Find the partial sum arrays along the selected axis. */
    var total = 0,
      partialsum = [],
      lookaheadsum = [],
      i,
      j,
      k,
      sum,
      index;
    if (maxw == rw) {
      for (i = vbox.r1; i <= vbox.r2; i++) {
        sum = 0;
        for (j = vbox.g1; j <= vbox.g2; j++) {
          for (k = vbox.b1; k <= vbox.b2; k++) {
            index = getColorIndex(i, j, k);
            sum += histo[index] || 0;
          }
        }
        total += sum;
        partialsum[i] = total;
      }
    } else if (maxw == gw) {
      for (i = vbox.g1; i <= vbox.g2; i++) {
        sum = 0;
        for (j = vbox.r1; j <= vbox.r2; j++) {
          for (k = vbox.b1; k <= vbox.b2; k++) {
            index = getColorIndex(j, i, k);
            sum += histo[index] || 0;
          }
        }
        total += sum;
        partialsum[i] = total;
      }
    } else {
      /* maxw == bw */
      for (i = vbox.b1; i <= vbox.b2; i++) {
        sum = 0;
        for (j = vbox.r1; j <= vbox.r2; j++) {
          for (k = vbox.g1; k <= vbox.g2; k++) {
            index = getColorIndex(j, k, i);
            sum += histo[index] || 0;
          }
        }
        total += sum;
        partialsum[i] = total;
      }
    }
    partialsum.forEach(function (d, i) {
      lookaheadsum[i] = total - d;
    });
    function doCut(color) {
      var dim1 = color + "1",
        dim2 = color + "2",
        left,
        right,
        vbox1,
        vbox2,
        d2,
        count2 = 0;
      for (i = vbox[dim1]; i <= vbox[dim2]; i++) {
        if (partialsum[i] > total / 2) {
          vbox1 = vbox.copy();
          vbox2 = vbox.copy();
          left = i - vbox[dim1];
          right = vbox[dim2] - i;
          if (left <= right) d2 = Math.min(vbox[dim2] - 1, ~~(i + right / 2));
          else d2 = Math.max(vbox[dim1], ~~(i - 1 - left / 2));
          // avoid 0-count boxes
          while (!partialsum[d2]) d2++;
          count2 = lookaheadsum[d2];
          while (!count2 && partialsum[d2 - 1]) count2 = lookaheadsum[--d2];
          // set dimensions
          vbox1[dim2] = d2;
          vbox2[dim1] = vbox1[dim2] + 1;
          //                    console.log('vbox counts:', vbox.count(), vbox1.count(), vbox2.count());
          return [vbox1, vbox2];
        }
      }
    }
    // determine the cut planes
    return maxw == rw ? doCut("r") : maxw == gw ? doCut("g") : doCut("b");
  }

  function quantize(pixels, maxcolors) {
    // short-circuit
    if (!pixels.length || maxcolors < 2 || maxcolors > 256) {
      //            console.log('wrong number of maxcolors');
      return false;
    }

    // XXX: check color content and convert to grayscale if insufficient

    var histo = getHisto(pixels),
      histosize = 1 << (3 * sigbits);

    // check that we aren't below maxcolors already
    var nColors = 0;
    histo.forEach(function () {
      nColors++;
    });
    if (nColors <= maxcolors) {
      // XXX: generate the new colors from the histo and return
    }

    // get the beginning vbox from the colors
    var vbox = vboxFromPixels(pixels, histo),
      pq = new PQueue(function (a, b) {
        return pv.naturalOrder(a.count(), b.count());
      });
    pq.push(vbox);

    // inner function to do the iteration
    function iter(lh, target) {
      var ncolors = 1,
        niters = 0,
        vbox;
      while (niters < maxIterations) {
        vbox = lh.pop();
        if (!vbox.count()) {
          /* just put it back */
          lh.push(vbox);
          niters++;
          continue;
        }
        // do the cut
        var vboxes = medianCutApply(histo, vbox),
          vbox1 = vboxes[0],
          vbox2 = vboxes[1];

        if (!vbox1) {
          //                    console.log("vbox1 not defined; shouldn't happen!");
          return;
        }
        lh.push(vbox1);
        if (vbox2) {
          /* vbox2 can be null */
          lh.push(vbox2);
          ncolors++;
        }
        if (ncolors >= target) return;
        if (niters++ > maxIterations) {
          //                    console.log("infinite loop; perhaps too few pixels!");
          return;
        }
      }
    }

    // first set of colors, sorted by population
    iter(pq, fractByPopulations * maxcolors);

    // Re-sort by the product of pixel occupancy times the size in color space.
    var pq2 = new PQueue(function (a, b) {
      return pv.naturalOrder(a.count() * a.volume(), b.count() * b.volume());
    });
    while (pq.size()) {
      pq2.push(pq.pop());
    }

    // next set - generate the median cuts using the (npix * vol) sorting.
    iter(pq2, maxcolors - pq2.size());

    // calculate the actual colors
    var cmap = new CMap();
    while (pq2.size()) {
      cmap.push(pq2.pop());
    }

    return cmap;
  }

  return {
    quantize: quantize,
  };
})();
